
/*List仅仅存储了当前节点，但提供了遍历的方法（节点中的前置后置指针，以及对它进行操作的迭代器）*/
template <typename Object>
class List
{
/*节点*/
private:
    struct Node
    {
        Object data;
        Node *prev; //虽然是嵌套Node，但并不是二叉树，而是前驱和后驱链表
        Node *next;
        /*左值构造函数*/
        Node(const Object & d = Object{}, Node *p = nullptr, Node *n = nullptr;) : data{d}, prev{p}, next{n} {}
        /*右值构造函数*/
        Node(Object && d, Node *p = nullptr, Node *n = nullptr) : data{ std::move(d) }, prev{ p }, next{n} {}
    };

/*列表的属性*/
private:
    int theSize;
    Node *head;
    Node *tail;

    void init()
    {
        theSize = 0;
        head = new Node;
        tail = new Node;
        head->next = tail;
        tail->prev = head;
    }

/*列表的节点迭代器*/
public:
    class const_iterator
    {
        /*私有部分（因为要继承）*/
        protected:
            /*当前节点*/
            Node *current;
            /*返回当前节点对象的引用*/
            Object & retrieve() const
                {return current->data; }
            /*含参构造函数*/
            const_iterator(Node *p) : current{p} {}

            /*友元类，让List可以访问迭代器内容*/
            friend class List<Object>;

        public:
            /*默认构造函数*/
            const_iterator() : current {nullptr} {}
            /*解引用运算符*/
            const Object & operator* () const
                { return retrieve(); }
            /*前置自增运算符（先增再返回）*/
            const_iterator & operator++ ()
            {
                current = current->next;
                return *this;
            }
            /*后置自增运算符（先返回再增）（int是专门用来区分的特殊标识符）*/
            const_iterator operator++ (int)
            {
                const_iterator old = *this;     //左值赋值运算符，old是引用，用于存储当前值
                ++(*this);                      //++写在左边，先递增再返回左值引用（本质是用普通前置后置++重载对象前置后置++）
                return old;                     //然后返回old中存储的没有递增的值
            }
            /*判断运算符*/
            bool operator== (const const_iterator & rhs) const
                { return current == rhs.current; }
            bool operator!= (const const_iterator & rhs) const
                { return !(*this == rhs); } //沿用上面的重载符
    }
    /*读写迭代器，公有继承*/
    class iterator: public const_iterator
    {
        protected:
            iterator(Node *p) : const_iterator {p} {}
            friend class List<Object>
        public:
            iterator() {} //默认构造函数
            /*解引用*/
            Object & operator* ()
                {return const_iterator::retrieve(); }
            const Object & operator*() const
                {return const_iterator::operator*(); }
            /*自增运算符*/
            iterator & operator++ ()
            {
                this->current = this->current_next;
                return *this;   
            }
            iterator operator++( int )
            {
                iterator old = *this;
                ++(*this);
                return old;
            }
    }

/*列表的方法*/
public:
    /*初始化*/
    List() { init(); }
    /*复制初始化*/
    List( const List & rhs)
    {
        init();
        for (auto & x : rhs)
            push_back(x);
    }
    /*析构函数*/
    ~List()
    {
        clear();
        delete head;
        delete tail;
    }
    /*左值赋值运算符*/
    List & operator= (const List& rhs)
    {
        List copy = rhs;
        std::swap(*this, copy);
        return *this;
    }
    /*右值构造函数*/
    List (List && rhs) : theSize { rhs.theSize} , head{ rhs.head }, tail{ rhs.tail }
    {
        rhs.theSize = 0;
        rhs.head = nullptr;
        rhs.tail = nullptr;
    }
    /*右值赋值运算符*/
    List & operator= (List && rhs)
    {
        std::swap( theSize, rhs.theSize );
        std::swap(head, rhs.head);
        std::swap(tail, rhs.tail);

        return *this;
    }

    iterator begin()
        { return { head->next }; }
    const_iterator begin() const
        { return { head->next }; }
    iterator end()
        { return {tail}; }
    const_iterator end() const
        { return {tail}; }

    /*获取基本属性*/
    int size() const
        { return theSize; }
    bool empty() const
        { return size() == 0; }
    
    /*迭代器无参操作*/
    /*清除所有列表节点*/
    void clear()
    {
        while( !empty() )
            pop_front();
    }
    Object & front()
        {return *begin(); }
    const Object & front() const
        {return *begin(); }
    Object & back()
        {return *--end(); }
    const Object & back() const
        {return *--end(); }
    
    void push_front ( const Object & x )
        { insert( begin(), x ); }
    void push_front ( Object && x )
        { insert( begin(), x ); }
    void push_back ( const Object & x )
        { insert( end(), x ); }
    void push_back ( Object && x )
        { insert( end(), x ); }
    void pop_front()
        { erase( begin() ); }
    void pop_back()
        { erase( --end() ); }

    /*插入操作*/
    /*在指定的迭代器处插入新节点，*/
    iterator insert( iterator itr, const Object & x )
    {
        Node *p = itr.current;  //默认赋值，浅拷贝
        theSize++;
        return { p->prev = p->prev->next = new Node{ x, p->prev, p } }; //链式赋值，首先执行后面的等号，然后执行前面的等号，最后执行return p->prev
    }
    iterator insert( iterator itr, Ojbect && x )
    {
        Node *p = itr.current;
        theSize++;
        return { p->prev = p->prev->next = new Node{ std::move(x), p->prev, p } };
    }

    /*删除操作*/
    /*在指定的迭代器处删除节点，并返回下一个节点的迭代器*/
    iterator erase( iterator itr )
    {
        Node *p = itr.current;
        iterator reVal { p->next };
        p->prev->next = p->next;
        p->next->prev = p->prev;
        delete p;
        theSize--;

        return reVal;
    }
    /*删除两个迭代器中的所有节点*/
    iterator erase (iterator from, iterator to)
    {
        for( iterator itr = from; itr != to; )
            itr = erase(itr);
        return to;
    }
};

